﻿using System;
using System.Collections.Generic;
using System.Text;
using System.IO;
using System.Security.Cryptography;

// This code is based completly on the work of Scott Garland. 
// All rights reserved to the original author.
namespace BigNumber
{
  //using System.UInt32 = System.UInt32; // This could be UInt32, UInt16 or Byte; not UInt64.

  #region DigitsArray
  [Serializable]
  internal class DigitsArray
  {
    internal DigitsArray(int size)
    {
      Allocate(size, 0);
    }

    internal DigitsArray(int size, int used)
    {
      Allocate(size, used);
    }

    internal DigitsArray(System.UInt32[] copyFrom)
    {
      Allocate(copyFrom.Length);
      CopyFrom(copyFrom, 0, 0, copyFrom.Length);
      RemoveLeadingZeroes();
    }

    internal DigitsArray(DigitsArray copyFrom)
    {
      Allocate(copyFrom.Count, copyFrom.DataUsed);
      Array.Copy(copyFrom.m_data, 0, m_data, 0, copyFrom.Count);
    }

    private System.UInt32[] m_data;

    internal static readonly System.UInt32 AllBits;		// = ~((System.UInt32)0);
    internal static readonly System.UInt32 HiBitSet;	// = 0x80000000;
    internal static int DataSizeOf
    {
      get { return sizeof(System.UInt32); }
    }

    internal static int DataSizeBits
    {
      get { return sizeof(System.UInt32) * 8; }
    }

    static DigitsArray()
    {
      unchecked
      {
        AllBits = (System.UInt32)~((System.UInt32)0);
        HiBitSet = (System.UInt32)(((System.UInt32)1) << (DataSizeBits) - 1);
      }
    }

    internal void Allocate(int size)
    {
      Allocate(size, 0);
    }

    internal void Allocate(int size, int used)
    {
      m_data = new System.UInt32[size];
      DataUsed = used;
    }

    internal void CopyFrom(System.UInt32[] source, int sourceOffset, int offset, int length)
    {
      if (source == m_data)
        throw new ArgumentException("CopyFrom - source cannot be equal to m_data");
      Array.Copy(source, sourceOffset, m_data, 0, length);
    }

    internal void CopyTo(System.UInt32[] array, int offset, int length)
    {
      if (array == m_data)
        throw new ArgumentException("CopyFrom - source cannot be equal to m_data");

      Array.Copy(m_data, 0, array, offset, length);
    }

    internal System.UInt32 this[int index]
    {
      get
      {
        if (index < DataUsed && index >= 0) 
          return m_data[index];
        return 0;
      }
      set 
      { 
        m_data[index] = value; 
      }
    }

    internal int DataUsed { get; set; }

    internal int Count
    {
      get { return m_data.Length; }
    }

    internal bool IsZero
    {
      get { return DataUsed == 0 || (DataUsed == 1 && m_data[0] == 0); }
    }

    internal bool IsOne
    {
      get
      {
        return (DataUsed == 1 && m_data[0] == 1);
      }
    }

    internal void RemoveLeadingZeroes()
    {
      DataUsed = m_data.Length;
      while (DataUsed > 1 && m_data[DataUsed - 1] == 0)
      {
         --DataUsed;
      }

      if (DataUsed == 0)
      {
          DataUsed = 1;
      }
    }

    internal int ShiftRight(int shiftCount)
    {
      return ShiftRight(m_data, shiftCount);
    }

    internal static int ShiftRight(System.UInt32[] buffer, int shiftCount)
    {
      int bufLen = buffer.Length;

      while (bufLen > 1 && buffer[bufLen - 1] == 0)
      {
        bufLen--;
      }

      int fullShift = shiftCount / DigitsArray.DataSizeBits;
      int partShift = shiftCount % DigitsArray.DataSizeBits;
      int target = 0;
      int source = fullShift;
      System.UInt32 mask = 1;
      mask = mask << partShift;
      mask--;

      System.UInt32 top = 0;
      int shiftComplement = DigitsArray.DataSizeBits - partShift;
      while (source < bufLen)
      {
        if (target > 0)
        {
          top = buffer[source] & mask;
          top = top << shiftComplement;
          buffer[target - 1] = buffer[target - 1] | top;
        }
        buffer[target] = buffer[source] >> partShift;
        target++;
        source++;
      }

      while (bufLen > 1 && buffer[bufLen - 1] == 0)
      {
        bufLen--;
      }

      return bufLen;
    }

    internal int ShiftLeft(int shiftCount)
    {
      return ShiftLeft(m_data, shiftCount);
    }

    internal static int ShiftLeft(System.UInt32[] buffer, int shiftCount)
    {
      int shiftAmount = DigitsArray.DataSizeBits;
      int bufLen = buffer.Length;

      while (bufLen > 1 && buffer[bufLen - 1] == 0)
      {
        bufLen--;
      }

      for (int count = shiftCount; count > 0; count -= shiftAmount)
      {
        if (count < shiftAmount)
        {
          shiftAmount = count;
        }

        ulong carry = 0;
        for (int i = 0; i < bufLen; i++)
        {
          ulong val = ((ulong)buffer[i]) << shiftAmount;
          val |= carry;

          buffer[i] = (System.UInt32)(val & DigitsArray.AllBits);
          carry = (val >> DigitsArray.DataSizeBits);
        }

        if (carry != 0)
        {
          if (bufLen + 1 <= buffer.Length)
          {
            buffer[bufLen] = (System.UInt32)carry;
            bufLen++;
            carry = 0;
          }
          else
          {
            throw new OverflowException();
          }
        }
      }
      return bufLen;
    }

    internal int ShiftLeftWithoutOverflow(int shiftCount)
    {
      List<System.UInt32> temporary = new List<System.UInt32>(m_data);
      int shiftAmount = DigitsArray.DataSizeBits;

      for (int count = shiftCount; count > 0; count -= shiftAmount)
      {
        if (count < shiftAmount)
        {
          shiftAmount = count;
        }

        ulong carry = 0;
        for (int i = 0; i < temporary.Count; i++)
        {
          ulong val = ((ulong)temporary[i]) << shiftAmount;
          val |= carry;

          temporary[i] = (System.UInt32)(val & DigitsArray.AllBits);
          carry = (val >> DigitsArray.DataSizeBits);
        }

        if (carry != 0)
        {
          temporary.Add(0);
          temporary[temporary.Count - 1] = (System.UInt32)carry;
        }
      }
      m_data = new System.UInt32[temporary.Count];
      temporary.CopyTo(m_data);
      return m_data.Length;
    }

    internal void Serialize(BinaryWriter writer)
    {
      foreach (UInt32 digit in m_data)
      {
        writer.Write(digit);
      }
    }

    internal void Deserialize(BinaryReader reader,int count)
    {
      Allocate(count,count);
      for (int i = 0; i < count; i++)
        m_data[i] = reader.ReadUInt32();
      RemoveLeadingZeroes();
    }
  }
  #endregion

  [Serializable]
  public class FastBigNumber : IIntegerBigNumber, IComparable<FastBigNumber>
  {
    private DigitsArray m_digits;
    private bool m_Negative = false;

    #region Constructors
    /// <summary>
    /// Create a FastBigNumber with an integer value of 0.
    /// </summary>
    public FastBigNumber()
    {
      m_digits = new DigitsArray(1, 1);
    }

    internal FastBigNumber(FastBigNumber number)
    {
      m_digits = new DigitsArray(number.m_digits);
      m_Negative = number.IsNegative;
    }
    /// <summary>
    /// Creates a FastBigNumber with the value of the operand.
    /// </summary>
    /// <param name="number">A long.</param>
    public FastBigNumber(long number)
    {
      if (number < 0)
        m_Negative = true;
      else
        m_Negative = false;

      number = Math.Abs(number);
      int size = sizeof(long) / DigitsArray.DataSizeOf;
      m_digits = new DigitsArray(size,size);
      int i=0;
      while (number > 0)
      {
        m_digits[i] = (System.UInt32)(number & (long)DigitsArray.AllBits);
        i++;
        number = number >> DigitsArray.DataSizeBits;
      }
      m_digits.RemoveLeadingZeroes();
    }

    /// <summary>
    /// Creates a FastBigNumber with the value of the operand. Can never be negative.
    /// </summary>
    /// <param name="number">A unsigned long.</param>
    public FastBigNumber(ulong number)
    {
      m_Negative = false;
      int size = sizeof(ulong) / DigitsArray.DataSizeOf;
      m_digits = new DigitsArray(size, size);
      int i = 0;
      while (number > 0)
      {
        m_digits[i] = (System.UInt32)(number & (ulong)DigitsArray.AllBits);
        i++;
        number = number >> DigitsArray.DataSizeBits;
      }
      m_digits.RemoveLeadingZeroes();
    }

    /// <summary>
    /// Creates a FastBigNumber initialized from the byte array.
    /// </summary>
    /// <param name="array"></param>
    private FastBigNumber(byte[] array)
    {
      ConstructFrom(array, 0, array.Length);
    }

    /// <summary>
    /// Creates a FastBigNumber initialized from the byte array ending at <paramref name="length" />.
    /// </summary>
    /// <param name="array">A byte array.</param>
    /// <param name="length">Int number of bytes to use.</param>
    private FastBigNumber(byte[] array, int length)
    {
      ConstructFrom(array, 0, length);
    }

    /// <summary>
    /// Creates a FastBigNumber initialized from <paramref name="length" /> bytes starting at <paramref name="offset" />.
    /// </summary>
    /// <param name="array">A byte array.</param>
    /// <param name="offset">Int offset into the <paramref name="array" />.</param>
    /// <param name="length">Int number of bytes.</param>
    private FastBigNumber(byte[] array, int offset, int length)
    {
      ConstructFrom(array, offset, length);
    }

    private void ConstructFrom(byte[] array, int offset, int length)
    {
      if (array == null)
      {
        throw new ArgumentNullException("array");
      }
      if (offset > array.Length || length > array.Length)
      {
        throw new ArgumentOutOfRangeException("offset");
      }
      if (length > array.Length || (offset + length) > array.Length)
      {
        throw new ArgumentOutOfRangeException("length");
      }

      int estSize = length / 4;
      int leftOver = length & 3;
      if (leftOver != 0)
      {
        ++estSize;
      }

      m_digits = new DigitsArray(estSize + 1, 0); // alloc one extra since we can't init -'s from here.

      for (int i = offset + length - 1, j = 0; (i - offset) >= 3; i -= 4, j++)
      {
        m_digits[j] = (System.UInt32)((array[i - 3] << 24) + (array[i - 2] << 16) + (array[i - 1] << 8) + array[i]);
        m_digits.DataUsed++;
      }

      System.UInt32 accumulator = 0;
      for (int i = leftOver; i > 0; i--)
      {
        System.UInt32 digit = array[offset + leftOver - i];
        digit = (digit << ((i - 1) * 8));
        accumulator |= digit;
      }
      m_digits[m_digits.DataUsed] = accumulator;

      m_digits.RemoveLeadingZeroes();
    }

    /// <summary>
    /// Creates a FastBigNumber in base-10 from the parameter.
    /// </summary>
    /// <remarks>
    ///  The new FastBigNumber is negative if the <paramref name="digits" /> has a leading - (minus).
    /// </remarks>
    /// <param name="digits">A string</param>
    public FastBigNumber(string digits)
    {
      if (digits == null) digits = "0";
      Construct(digits, 10);
    }


    private void Construct(string digits, int radix)
    {
      if (digits == null)
      {
        throw new ArgumentNullException("digits");
      }

      if (digits == String.Empty)
        digits = "0";
      FastBigNumber multiplier = new FastBigNumber(1);
      FastBigNumber result = new FastBigNumber();
      digits = digits.ToUpper(System.Globalization.CultureInfo.CurrentCulture).Trim();

      int nDigits = (digits[0] == '-' ? 1 : 0);

      for (int idx = digits.Length - 1; idx >= nDigits; idx--)
      {
        int d = (int)digits[idx];
        if (d >= '0' && d <= '9')
        {
          d -= '0';
        }
        else if (d >= 'A' && d <= 'Z')
        {
          d = (d - 'A') + 10;
        }
        else
        {
          throw new ArgumentOutOfRangeException("digits");
        }

        if (d >= radix)
        {
          throw new ArgumentOutOfRangeException("digits");
        }
        result += (multiplier * d);
        multiplier *= radix;
      }

      if (digits[0] == '-')
      {
        m_Negative = true;
      }

      this.m_digits = result.m_digits;
    }

    /// <summary>
    /// Copy constructor, doesn't copy the digits parameter, assumes <code>this</code> owns the DigitsArray.
    /// </summary>
    /// <remarks>The <paramef name="digits" /> parameter is saved and reset.</remarks>
    /// <param name="digits"></param>
    private FastBigNumber(DigitsArray digits)
    {
      digits.RemoveLeadingZeroes();
      this.m_digits = digits;
    }

    public void Initialize(string digits)
    {
      if (digits == null) digits = "0";
      Construct(digits, 10);
    }
    #endregion

    #region Public Properties
    /// <summary>
    /// A bool value that is true when the FastBigNumber is negative (less than zero).
    /// </summary>
    /// <value>
    /// A bool value that is true when the FastBigNumber is negative (less than zero).
    /// </value>
    public bool IsNegative 
    { 
      get 
      {
        return m_Negative; 
      }
      internal set 
      {
        if (!IsZero)
          m_Negative = value;
      }
    }

    /// <summary>
    /// A bool value that is true when the FastBigNumber is exactly zero.
    /// </summary>
    /// <value>
    /// A bool value that is true when the FastBigNumber is exactly zero.
    /// </value>
    public bool IsZero { get { return m_digits.IsZero; } }

    public bool IsOne { get { return m_digits.IsOne; } }

    public StdBigNumber ToStdBigNumber
    {
      get
      {
        return new StdBigNumber(this.ToString());
      }
    }
    #endregion

    #region Implicit Type Operators Overloads

    /// <summary>
    /// Creates a FastBigNumber from a long.
    /// </summary>
    /// <param name="value">A long.</param>
    /// <returns>A FastBigNumber initialzed by <paramref name="value" />.</returns>
    public static implicit operator FastBigNumber(long value)
    {
      return (new FastBigNumber(value));
    }

    /// <summary>
    /// Creates a FastBigNumber from a ulong.
    /// </summary>
    /// <param name="value">A ulong.</param>
    /// <returns>A FastBigNumber initialzed by <paramref name="value" />.</returns>
    public static implicit operator FastBigNumber(ulong value)
    {
      return (new FastBigNumber(value));
    }

    /// <summary>
    /// Creates a FastBigNumber from a int.
    /// </summary>
    /// <param name="value">A int.</param>
    /// <returns>A FastBigNumber initialzed by <paramref name="value" />.</returns>
    public static implicit operator FastBigNumber(int value)
    {
      return (new FastBigNumber((long)value));
    }

    /// <summary>
    /// Creates a FastBigNumber from a uint.
    /// </summary>
    /// <param name="value">A uint.</param>
    /// <returns>A FastBigNumber initialzed by <paramref name="value" />.</returns>
    public static implicit operator FastBigNumber(uint value)
    {
      return (new FastBigNumber((ulong)value));
    }


    public static implicit operator FastBigNumber(string value)
    {
      return (new FastBigNumber(value));
    }

    #endregion

    #region Addition and Subtraction Operator Overloads
    /// <summary>
    /// Adds two FastBigNumbers and returns a new FastBigNumber that represents the sum.
    /// </summary>
    /// <param name="leftSide">A FastBigNumber</param>
    /// <param name="rightSide">A FastBigNumber</param>
    /// <returns>The FastBigNumber result of adding <paramref name="leftSide" /> and <paramref name="rightSide" />.</returns>
    public static FastBigNumber operator +(FastBigNumber leftSide, FastBigNumber rightSide)
    {
      if (ReferenceEquals(leftSide, null)) throw new ArgumentNullException("leftSide");
      if (ReferenceEquals(rightSide, null)) throw new ArgumentNullException("rightSide");
      return Add(leftSide, rightSide);
    }

    /// <summary>
    /// Adds two FastBigNumbers and returns a new FastBigNumber that represents the sum.
    /// </summary>
    /// <param name="leftSide">A FastBigNumber</param>
    /// <param name="rightSide">A FastBigNumber</param>
    /// <returns>The FastBigNumber result of adding <paramref name="leftSide" /> and <paramref name="rightSide" />.</returns>
    private static FastBigNumber Add(FastBigNumber leftSide, FastBigNumber rightSide)
    {
      if (leftSide.IsZero)
        return new FastBigNumber(rightSide);
      if (rightSide.IsZero)
        return new FastBigNumber(leftSide);

      #region Handle negative numbers
      if (leftSide.IsNegative && rightSide.IsNegative)
      {
        rightSide.Negate();
        if (!object.ReferenceEquals(leftSide, rightSide)) //In case we activated the function on this
          leftSide.Negate();
        FastBigNumber innerResult = Add(leftSide, rightSide);
        rightSide.Negate();
        if (!object.ReferenceEquals(leftSide, rightSide))
          leftSide.Negate();//In case we activated the function on this
        innerResult.Negate();
        return innerResult;
      }
      else
        if (leftSide.IsNegative)
        {
          leftSide.Negate();
          FastBigNumber innerResult = Subtract(rightSide, leftSide);
          leftSide.Negate();
          return innerResult;
        }
        else
          if (rightSide.IsNegative)
          {
            rightSide.Negate();
            FastBigNumber innerResult = Subtract(leftSide, rightSide);
            rightSide.Negate();
            return innerResult;
          }
      #endregion

      int size = System.Math.Max(leftSide.m_digits.DataUsed, rightSide.m_digits.DataUsed);
      DigitsArray da = new DigitsArray(size + 1);

      long carry = 0;
      for (int i = 0; i < da.Count; i++)
      {
        long sum = (long)leftSide.m_digits[i] + (long)rightSide.m_digits[i] + carry;
        carry = (long)(sum >> DigitsArray.DataSizeBits);
        da[i] = (System.UInt32)(sum & DigitsArray.AllBits);
      }

      return new FastBigNumber(da);
    }

    /// <summary>
    /// Increments the FastBigNumber operand by 1.
    /// </summary>
    /// <param name="leftSide">The FastBigNumber operand.</param>
    /// <returns>The value of <paramref name="leftSide" /> incremented by 1.</returns>
    public static FastBigNumber operator ++(FastBigNumber leftSide)
    {
      if (ReferenceEquals(leftSide, null)) throw new ArgumentNullException("leftSide");
      //if (ReferenceEquals(rightSide, null)) throw new ArgumentNullException("rightSide");

      return Increment(leftSide);
    }

    /// <summary>
    /// Increments the FastBigNumber operand by 1.
    /// </summary>
    /// <param name="leftSide">The FastBigNumber operand.</param>
    /// <returns>The value of <paramref name="leftSide" /> incremented by 1.</returns>
    private static FastBigNumber Increment(FastBigNumber leftSide)
    {
      return (leftSide + 1);
    }

    /// <summary>
    /// Substracts two FastBigNumbers and returns a new FastBigNumber that represents the sum.
    /// </summary>
    /// <param name="leftSide">A FastBigNumber</param>
    /// <param name="rightSide">A FastBigNumber</param>
    /// <returns>The FastBigNumber result of substracting <paramref name="leftSide" /> and <paramref name="rightSide" />.</returns>
    public static FastBigNumber operator -(FastBigNumber leftSide, FastBigNumber rightSide)
    {
      if (ReferenceEquals(leftSide, null)) throw new ArgumentNullException("leftSide");
      if (ReferenceEquals(rightSide, null)) throw new ArgumentNullException("rightSide");

      return Subtract(leftSide, rightSide);
    }

    /// <summary>
    /// Substracts two FastBigNumbers and returns a new FastBigNumber that represents the sum.
    /// </summary>
    /// <param name="leftSide">A FastBigNumber</param>
    /// <param name="rightSide">A FastBigNumber</param>
    /// <returns>The FastBigNumber result of substracting <paramref name="leftSide" /> and <paramref name="rightSide" />.</returns>
    private static FastBigNumber Subtract(FastBigNumber leftSide, FastBigNumber rightSide)
    {
      if (rightSide.IsZero)
        return new FastBigNumber(leftSide);
      if (leftSide.IsZero)
      {
        FastBigNumber result = new FastBigNumber(rightSide);
        result.Negate();
        return result;
      }
      #region Handle Negative Numbers
      if (leftSide.IsNegative || rightSide.IsNegative)
      {
        rightSide.Negate();
        FastBigNumber innerResult = Add(leftSide, rightSide);
        return innerResult;
      }
      #endregion

      //Subtract only when leftSide > rightSide
      if (leftSide.CompareTo(rightSide) < 0)
      {
        FastBigNumber innerResult = Subtract(rightSide, leftSide);
        innerResult.Negate();
        return innerResult;
      }

      int size = System.Math.Max(leftSide.m_digits.DataUsed, rightSide.m_digits.DataUsed) + 1;
      DigitsArray da = new DigitsArray(size);

      long carry = 0;
      for (int i = 0; i < da.Count; i++)
      {
        long diff = (long)leftSide.m_digits[i] - (long)rightSide.m_digits[i] - carry;
        da[i] = (System.UInt32)(diff & DigitsArray.AllBits);
        da.DataUsed++;
        carry = ((diff < 0) ? 1 : 0);
      }
      return new FastBigNumber(da);
    }

    /// <summary>
    /// Decrements the FastBigNumber operand by 1.
    /// </summary>
    /// <param name="leftSide">The FastBigNumber operand.</param>
    /// <returns>The value of the <paramref name="leftSide" /> decremented by 1.</returns>
    public static FastBigNumber operator --(FastBigNumber leftSide)
    {
      if (ReferenceEquals(leftSide, null)) throw new ArgumentNullException("leftSide");
//      if (ReferenceEquals(rightSide, null)) throw new ArgumentNullException("rightSide");
      return Decrement(leftSide);
    }

    /// <summary>
    /// Decrements the FastBigNumber operand by 1.
    /// </summary>
    /// <param name="leftSide">The FastBigNumber operand.</param>
    /// <returns>The value of the <paramref name="leftSide" /> decremented by 1.</returns>
    private static FastBigNumber Decrement(FastBigNumber leftSide)
    {
      return (leftSide - 1);
    }
    #endregion

    #region Negate Operator Overload

    private void Abs()
    {
      m_Negative = false;
    }

    /// <summary>
    /// Negates the FastBigNumber, that is, if the FastBigNumber is negative return a positive FastBigNumber, and if the
    /// FastBigNumber is negative return the postive.
    /// </summary>
    /// <param name="leftSide">A FastBigNumber operand.</param>
    /// <returns>The value of the <paramref name="this" /> negated.</returns>
    public static FastBigNumber operator -(FastBigNumber leftSide)
    {
      if (ReferenceEquals(leftSide, null)) throw new ArgumentNullException("leftSide");
      //if (ReferenceEquals(rightSide, null)) throw new ArgumentNullException("rightSide");

      FastBigNumber result = new FastBigNumber(leftSide);
      result.Negate();
      return result;
    }

    /// <summary>
    /// Negates the FastBigNumber, that is, if the FastBigNumber is negative return a positive FastBigNumber, and if the
    /// FastBigNumber is negative return the postive.
    /// </summary>
    /// <returns>The value of the <paramref name="this" /> negated.</returns>
    public void Negate()
    {
      if (IsZero)
        m_Negative = false;
      m_Negative = !m_Negative;
    }

    #endregion

    #region Multiplication, Division and Modulus Operators
    /// <summary>
    /// Multiply two FastBigNumbers returning the result.
    /// </summary>
    /// <remarks>
    /// See Knuth.
    /// </remarks>
    /// <param name="leftSide">A FastBigNumber.</param>
    /// <param name="rightSide">A FastBigNumber</param>
    /// <returns></returns>
    public static FastBigNumber operator *(FastBigNumber leftSide, FastBigNumber rightSide)
    {
      if (ReferenceEquals(leftSide, null)) throw new ArgumentNullException("leftSide");
      if (ReferenceEquals(rightSide, null)) throw new ArgumentNullException("rightSide");
      return Multiply(leftSide, rightSide);
    }

    /// <summary>
    /// Multiply two FastBigNumbers returning the result.
    /// </summary>
    /// <param name="leftSide">A FastBigNumber.</param>
    /// <param name="rightSide">A FastBigNumber</param>
    /// <returns></returns>
    private static FastBigNumber Multiply(FastBigNumber leftSide, FastBigNumber rightSide)
    {
      if (object.ReferenceEquals(leftSide, null))
      {
        throw new ArgumentNullException("leftSide");
      }
      if (object.ReferenceEquals(rightSide, null))
      {
        throw new ArgumentNullException("rightSide");
      }

      bool leftSideNeg = leftSide.IsNegative;
      bool rightSideNeg = rightSide.IsNegative;

      leftSide.Abs();
      rightSide.Abs();

      DigitsArray da = new DigitsArray(leftSide.m_digits.DataUsed + rightSide.m_digits.DataUsed);
      da.DataUsed = da.Count;

      for (int i = 0; i < leftSide.m_digits.DataUsed; i++)
      {
        ulong carry = 0;
        for (int j = 0, k = i; j < rightSide.m_digits.DataUsed; j++, k++)
        {
          ulong val = ((ulong)leftSide.m_digits[i] * (ulong)rightSide.m_digits[j]) + (ulong)da[k] + carry;

          da[k] = (System.UInt32)(val & DigitsArray.AllBits);
          carry = (val >> DigitsArray.DataSizeBits);
        }

        if (carry != 0)
        {
          da[i + rightSide.m_digits.DataUsed] = (System.UInt32)carry;
        }
      }

      //da.ResetDataUsed();
      FastBigNumber result = new FastBigNumber(da);
      return (leftSideNeg != rightSideNeg ? -result : result);     
    }

    /// <summary>
    /// Divide a FastBigNumber by another FastBigNumber and returning the result.
    /// </summary>
    /// <param name="leftSide">A FastBigNumber divisor.</param>
    /// <param name="rightSide">A FastBigNumber dividend.</param>
    /// <returns>The FastBigNumber result.</returns>
    public static FastBigNumber operator /(FastBigNumber leftSide, FastBigNumber rightSide)
    {
      if (ReferenceEquals(leftSide, null)) throw new ArgumentNullException("leftSide");
      if (ReferenceEquals(rightSide, null)) throw new ArgumentNullException("rightSide");

      return Divide(leftSide, rightSide);
    }

    /// <summary>
    /// Divide a FastBigNumber by another FastBigNumber and returning the result.
    /// </summary>
    /// <param name="leftSide">A FastBigNumber divisor.</param>
    /// <param name="rightSide">A FastBigNumber dividend.</param>
    /// <returns>The FastBigNumber result.</returns>
    private static FastBigNumber Divide(FastBigNumber leftSide, FastBigNumber rightSide)
    {
      if (leftSide == null)
      {
        throw new ArgumentNullException("leftSide");
      }
      if (rightSide == null)
      {
        throw new ArgumentNullException("rightSide");
      }

      if (rightSide.IsZero)
      {
        throw new DivideByZeroException();
      }

      bool divisorNeg = rightSide.IsNegative;
      bool dividendNeg = leftSide.IsNegative;

      leftSide.Abs();
      rightSide.Abs();

      if (leftSide < rightSide)
      {
        return new FastBigNumber(0);
      }

      FastBigNumber quotient;
      FastBigNumber remainder;
      Divide(leftSide, rightSide, out quotient, out remainder);

      return (dividendNeg != divisorNeg ? -quotient : quotient);     
    }

    private static void Divide(FastBigNumber leftSide, FastBigNumber rightSide, out FastBigNumber quotient, out FastBigNumber remainder)
    {
      if (leftSide.IsZero)
      {
        quotient = new FastBigNumber();
        remainder = new FastBigNumber();
        return;
      }

      if (rightSide.m_digits.DataUsed == 1)
      {
        SingleDivide(leftSide, rightSide, out quotient, out remainder);
      }
      else
      {
        MultiDivide(leftSide, rightSide, out quotient, out remainder);
      }
    }

    private static void MultiDivide(FastBigNumber leftSide, FastBigNumber rightSide, out FastBigNumber quotient, out FastBigNumber remainder)
    {
      bool leftNegative = leftSide.IsNegative;
      if (rightSide.IsZero)
      {
        throw new DivideByZeroException();
      }

      System.UInt32 val = rightSide.m_digits[rightSide.m_digits.DataUsed - 1];
      int d = 0;
      for (uint mask = DigitsArray.HiBitSet; mask != 0 && (val & mask) == 0; mask >>= 1)
      {
        d++;
      }

      int remainderLen = leftSide.m_digits.DataUsed + 1;
      System.UInt32[] remainderDat = new System.UInt32[remainderLen];
      leftSide.m_digits.CopyTo(remainderDat, 0, leftSide.m_digits.DataUsed);

      DigitsArray.ShiftLeft(remainderDat, d);
      rightSide = rightSide << d;

      ulong firstDivisor = rightSide.m_digits[rightSide.m_digits.DataUsed - 1];
      ulong secondDivisor = (rightSide.m_digits.DataUsed < 2 ? (System.UInt32)0 : rightSide.m_digits[rightSide.m_digits.DataUsed - 2]);

      int divisorLen = rightSide.m_digits.DataUsed + 1;
      DigitsArray dividendPart = new DigitsArray(divisorLen, divisorLen);
      System.UInt32[] result = new System.UInt32[leftSide.m_digits.Count + 1];
      int resultPos = 0;

      ulong carryBit = (ulong)0x1 << DigitsArray.DataSizeBits; // 0x100000000
      for (int j = remainderLen - rightSide.m_digits.DataUsed, pos = remainderLen - 1; j > 0; j--, pos--)
      {
        ulong dividend = ((ulong)remainderDat[pos] << DigitsArray.DataSizeBits) + (ulong)remainderDat[pos - 1];
        ulong qHat = (dividend / firstDivisor);
        ulong rHat = (dividend % firstDivisor);

        while (pos >= 2)
        {
          if (qHat == carryBit || (qHat * secondDivisor) > ((rHat << DigitsArray.DataSizeBits) + remainderDat[pos - 2]))
          {
            qHat--;
            rHat += firstDivisor;
            if (rHat < carryBit)
            {
              continue;
            }
          }
          break;
        }

        for (int h = 0; h < divisorLen; h++)
        {
          dividendPart[divisorLen - h - 1] = remainderDat[pos - h];
        }

        FastBigNumber dTemp = new FastBigNumber(dividendPart);
        FastBigNumber rTemp = rightSide * (long)qHat;
        while (rTemp > dTemp)
        {
          qHat--;
          rTemp -= rightSide;
        }

        rTemp = dTemp - rTemp;
        for (int h = 0; h < divisorLen; h++)
        {
          remainderDat[pos - h] = rTemp.m_digits[rightSide.m_digits.DataUsed - h];
        }

        result[resultPos++] = (System.UInt32)qHat;
      }

      Array.Reverse(result, 0, resultPos);
      quotient = new FastBigNumber(new DigitsArray(result));

      int n = DigitsArray.ShiftRight(remainderDat, d);
      DigitsArray rDA = new DigitsArray(n, n);
      rDA.CopyFrom(remainderDat, 0, 0, rDA.DataUsed);
      remainder = new FastBigNumber(rDA);
      remainder.IsNegative = leftNegative;
    }

    private static void SingleDivide(FastBigNumber leftSide, FastBigNumber rightSide, out FastBigNumber quotient, out FastBigNumber remainder)
    {
      bool leftNegative = leftSide.IsNegative;
      if (rightSide.IsZero)
      {
        throw new DivideByZeroException();
      }

      DigitsArray remainderDigits = new DigitsArray(leftSide.m_digits);
      remainderDigits.RemoveLeadingZeroes();

      int pos = remainderDigits.DataUsed - 1;
      ulong divisor = (ulong)rightSide.m_digits[0];
      ulong dividend = (ulong)remainderDigits[pos];

      System.UInt32[] result = new System.UInt32[leftSide.m_digits.Count];
      leftSide.m_digits.CopyTo(result, 0, result.Length);
      int resultPos = 0;

      if (dividend >= divisor)
      {
        result[resultPos++] = (System.UInt32)(dividend / divisor);
        remainderDigits[pos] = (System.UInt32)(dividend % divisor);
      }
      pos--;

      while (pos >= 0)
      {
        dividend = ((ulong)(remainderDigits[pos + 1]) << DigitsArray.DataSizeBits) + (ulong)remainderDigits[pos];
        result[resultPos++] = (System.UInt32)(dividend / divisor);
        remainderDigits[pos + 1] = 0;
        remainderDigits[pos--] = (System.UInt32)(dividend % divisor);
      }
      remainder = new FastBigNumber(remainderDigits);
      remainder.IsNegative = leftNegative;

      DigitsArray quotientDigits = new DigitsArray(resultPos + 1, resultPos);
      int j = 0;
      for (int i = quotientDigits.DataUsed - 1; i >= 0; i--, j++)
      {
        quotientDigits[j] = result[i];
      }
      quotient = new FastBigNumber(quotientDigits);
    }

    /// <summary>
    /// Perform the modulus of a FastBigNumber with another FastBigNumber and return the result.
    /// </summary>
    /// <param name="leftSide">A FastBigNumber divisor.</param>
    /// <param name="rightSide">A FastBigNumber dividend.</param>
    /// <returns>The FastBigNumber result.</returns>
    public static FastBigNumber operator %(FastBigNumber leftSide, FastBigNumber rightSide)
    {
      if (ReferenceEquals(leftSide, null)) throw new ArgumentNullException("leftSide");
      if (ReferenceEquals(rightSide, null)) throw new ArgumentNullException("rightSide");

      return Modulus(leftSide,rightSide);
    }

    /// <summary>
    /// Perform the modulus of a FastBigNumber with another FastBigNumber and return the result.
    /// </summary>
    /// <param name="leftSide">A FastBigNumber divisor.</param>
    /// <param name="rightSide">A FastBigNumber dividend.</param>
    /// <returns>The FastBigNumber result.</returns>
    private static FastBigNumber Modulus(FastBigNumber leftSide, FastBigNumber rightSide)
    {
      bool leftNegative = leftSide.IsNegative;
      if (leftSide == null)
      {
        throw new ArgumentNullException("leftSide");
      }

      if (rightSide == null)
      {
        throw new ArgumentNullException("rightSide");
      }

      if (rightSide.IsZero)
      {
        throw new DivideByZeroException();
      }

      FastBigNumber quotient;
      FastBigNumber remainder;

      bool dividendNeg = leftSide.IsNegative;
      FastBigNumber tempLeftSide = BigNumberMath.Abs<FastBigNumber>(leftSide);
      FastBigNumber tempRightSide = BigNumberMath.Abs<FastBigNumber>(rightSide);

      if (tempLeftSide < tempRightSide)
      {
        return new FastBigNumber(leftSide);
      }

      Divide(leftSide, rightSide, out quotient, out remainder);
      remainder.IsNegative = leftNegative;
      return remainder; 
    }
    #endregion

    #region Bitwise Operator Overloads

    public static FastBigNumber operator &(FastBigNumber leftSide, FastBigNumber rightSide)
    {
      if (ReferenceEquals(leftSide, null)) throw new ArgumentNullException("leftSide");
      if (ReferenceEquals(rightSide, null)) throw new ArgumentNullException("rightSide");

      int len = System.Math.Max(leftSide.m_digits.DataUsed, rightSide.m_digits.DataUsed);
      DigitsArray da = new DigitsArray(len, len);
      for (int idx = 0; idx < len; idx++)
      {
        da[idx] = (System.UInt32)(leftSide.m_digits[idx] & rightSide.m_digits[idx]);
      }
      return new FastBigNumber(da);
    }

    private static FastBigNumber BitwiseAnd(FastBigNumber leftSide, FastBigNumber rightSide)
    {
      return leftSide & rightSide;
    }

    public static FastBigNumber operator |(FastBigNumber leftSide, FastBigNumber rightSide)
    {
      if (ReferenceEquals(leftSide, null)) throw new ArgumentNullException("leftSide");
      if (ReferenceEquals(rightSide, null)) throw new ArgumentNullException("rightSide");

      int len = System.Math.Max(leftSide.m_digits.DataUsed, rightSide.m_digits.DataUsed);
      DigitsArray da = new DigitsArray(len, len);
      for (int idx = 0; idx < len; idx++)
      {
        da[idx] = (System.UInt32)(leftSide.m_digits[idx] | rightSide.m_digits[idx]);
      }
      return new FastBigNumber(da);
    }

    private static FastBigNumber BitwiseOr(FastBigNumber leftSide, FastBigNumber rightSide)
    {
      return leftSide | rightSide;
    }

    public static FastBigNumber operator ^(FastBigNumber leftSide, FastBigNumber rightSide)
    {
      if (ReferenceEquals(leftSide, null)) throw new ArgumentNullException("leftSide");
      if (ReferenceEquals(rightSide, null)) throw new ArgumentNullException("rightSide");

      int len = System.Math.Max(leftSide.m_digits.DataUsed, rightSide.m_digits.DataUsed);
      DigitsArray da = new DigitsArray(len, len);
      for (int idx = 0; idx < len; idx++)
      {
        da[idx] = (System.UInt32)(leftSide.m_digits[idx] ^ rightSide.m_digits[idx]);
      }
      return new FastBigNumber(da);
    }

    private static FastBigNumber Xor(FastBigNumber leftSide, FastBigNumber rightSide)
    {
      return leftSide ^ rightSide;
    }

    public static FastBigNumber operator ~(FastBigNumber leftSide)
    {
      if (ReferenceEquals(leftSide, null)) throw new ArgumentNullException("leftSide");
      //if (ReferenceEquals(rightSide, null)) throw new ArgumentNullException("rightSide");

      DigitsArray da = new DigitsArray(leftSide.m_digits.Count);
      for (int idx = 0; idx < da.Count; idx++)
      {
        da[idx] = (System.UInt32)(~(leftSide.m_digits[idx]));
      }

      return new FastBigNumber(da);
    }

    private static FastBigNumber OnesComplement(FastBigNumber leftSide)
    {
      return ~leftSide;
    }

    #endregion

    #region Left and Right Shift Operator Overloads
    public static FastBigNumber operator <<(FastBigNumber leftSide, int shiftCount)
    {
      if (ReferenceEquals(leftSide, null)) throw new ArgumentNullException("leftSide");
      DigitsArray da = new DigitsArray(leftSide.m_digits);
      da.DataUsed = da.ShiftLeftWithoutOverflow(shiftCount);

      return new FastBigNumber(da);
    }

    private static FastBigNumber LeftShift(FastBigNumber leftSide, int shiftCount)
    {
      return leftSide << shiftCount;
    }

    public static FastBigNumber operator >>(FastBigNumber leftSide, int shiftCount)
    {
      if (ReferenceEquals(leftSide, null)) throw new ArgumentNullException("leftSide");
      //if (ReferenceEquals(rightSide, null)) throw new ArgumentNullException("rightSide");


      DigitsArray da = new DigitsArray(leftSide.m_digits);
      da.DataUsed = da.ShiftRight(shiftCount);

      if (leftSide.IsNegative)
      {
        for (int i = da.Count - 1; i >= da.DataUsed; i--)
        {
          da[i] = DigitsArray.AllBits;
        }

        System.UInt32 mask = DigitsArray.HiBitSet;
        for (int i = 0; i < DigitsArray.DataSizeBits; i++)
        {
          if ((da[da.DataUsed - 1] & mask) == DigitsArray.HiBitSet)
          {
            break;
          }
          da[da.DataUsed - 1] |= mask;
          mask >>= 1;
        }
        da.DataUsed = da.Count;
      }

      return new FastBigNumber(da);
    }

    private static FastBigNumber RightShift(FastBigNumber leftSide, int shiftCount)
    {
      if (leftSide == null)
      {
        throw new ArgumentNullException("leftSide");
      }

      return leftSide >> shiftCount;
    }
    #endregion

    #region Relational Operator Overloads

    /// <summary>
    /// Compare this instance to a specified object and returns indication of their relative value.
    /// </summary>
    /// <param name="value">An object to compare, or a null reference (<b>Nothing</b> in Visual Basic).</param>
    /// <returns>A signed number indicating the relative value of this instance and <i>value</i>.
    /// <list type="table">
    ///		<listheader>
    ///			<term>Return Value</term>
    ///			<description>Description</description>
    ///		</listheader>
    ///		<item>
    ///			<term>Less than zero</term>
    ///			<description>This instance is less than <i>value</i>.</description>
    ///		</item>
    ///		<item>
    ///			<term>Zero</term>
    ///			<description>This instance is equal to <i>value</i>.</description>
    ///		</item>
    ///		<item>
    ///			<term>Greater than zero</term>
    ///			<description>
    ///				This instance is greater than <i>value</i>. 
    ///				<para>-or-</para>
    ///				<i>value</i> is a null reference (<b>Nothing</b> in Visual Basic).
    ///			</description>
    ///		</item>
    /// </list>
    /// </returns>
    public int CompareTo(FastBigNumber value)
    {
      return Compare(this, value);
    }

    /// <summary>
    /// Compare two objects and return an indication of their relative value.
    /// </summary>
    /// <param name="leftSide">An object to compare, or a null reference (<b>Nothing</b> in Visual Basic).</param>
    /// <param name="rightSide">An object to compare, or a null reference (<b>Nothing</b> in Visual Basic).</param>
    /// <returns>A signed number indicating the relative value of this instance and <i>value</i>.
    /// <list type="table">
    ///		<listheader>
    ///			<term>Return Value</term>
    ///			<description>Description</description>
    ///		</listheader>
    ///		<item>
    ///			<term>Less than zero</term>
    ///			<description>This instance is less than <i>value</i>.</description>
    ///		</item>
    ///		<item>
    ///			<term>Zero</term>
    ///			<description>This instance is equal to <i>value</i>.</description>
    ///		</item>
    ///		<item>
    ///			<term>Greater than zero</term>
    ///			<description>
    ///				This instance is greater than <i>value</i>. 
    ///				<para>-or-</para>
    ///				<i>value</i> is a null reference (<b>Nothing</b> in Visual Basic).
    ///			</description>
    ///		</item>
    /// </list>
    /// </returns>
    public static int Compare(FastBigNumber leftSide, FastBigNumber rightSide)
    {

      if (object.ReferenceEquals(leftSide, rightSide))
      {
        return 0;
      }

      if (object.ReferenceEquals(leftSide, null))
      {
        throw new ArgumentNullException("leftSide");
      }

      if (object.ReferenceEquals(rightSide, null))
      {
        throw new ArgumentNullException("rightSide");
      }

      if (leftSide > rightSide) return 1;
      if (leftSide == rightSide) return 0;
      return -1;
    }

    public static bool operator ==(FastBigNumber leftSide, FastBigNumber rightSide)
    {
      if (object.ReferenceEquals(leftSide, rightSide))
      {
        return true;
      }

      if (object.ReferenceEquals(leftSide, null) || object.ReferenceEquals(rightSide, null))
      {
        return false;
      }

      if (leftSide.IsNegative != rightSide.IsNegative)
      {
        return false;
      }

      return leftSide.Equals(rightSide);
    }

    public static bool operator !=(FastBigNumber leftSide, FastBigNumber rightSide)
    {
      return !(leftSide == rightSide);
    }

    public static bool operator >(FastBigNumber leftSide, FastBigNumber rightSide)
    {
      if (object.ReferenceEquals(leftSide, null))
      {
        throw new ArgumentNullException("leftSide");
      }

      if (object.ReferenceEquals(rightSide, null))
      {
        throw new ArgumentNullException("rightSide");
      }

      if (leftSide.IsNegative != rightSide.IsNegative)
      {
        return rightSide.IsNegative;
      }

      if (leftSide.m_digits.DataUsed != rightSide.m_digits.DataUsed)
      {
        return leftSide.m_digits.DataUsed > rightSide.m_digits.DataUsed;
      }

      for (int idx = leftSide.m_digits.DataUsed - 1; idx >= 0; idx--)
      {
        if (leftSide.m_digits[idx] != rightSide.m_digits[idx])
        {
          return (leftSide.m_digits[idx] > rightSide.m_digits[idx]);
        }
      }
      return false;
    }

    public static bool operator <(FastBigNumber leftSide, FastBigNumber rightSide)
    {
      if (object.ReferenceEquals(leftSide, null))
      {
        throw new ArgumentNullException("leftSide");
      }

      if (object.ReferenceEquals(rightSide, null))
      {
        throw new ArgumentNullException("rightSide");
      }

      if (leftSide.IsNegative != rightSide.IsNegative)
      {
        return leftSide.IsNegative;
      }

      if (leftSide.m_digits.DataUsed != rightSide.m_digits.DataUsed)
      {
        return leftSide.m_digits.DataUsed < rightSide.m_digits.DataUsed;
      }

      for (int idx = leftSide.m_digits.DataUsed - 1; idx >= 0; idx--)
      {
        if (leftSide.m_digits[idx] != rightSide.m_digits[idx])
        {
          return (leftSide.m_digits[idx] < rightSide.m_digits[idx]);
        }
      }
      return false;
    }

    public static bool operator >=(FastBigNumber leftSide, FastBigNumber rightSide)
    {

      return Compare(leftSide, rightSide) >= 0;
    }

    public static bool operator <=(FastBigNumber leftSide, FastBigNumber rightSide)
    {
      return Compare(leftSide, rightSide) <= 0;
    }
    #endregion

    #region Object Overrides
    /// <summary>
    /// Determines whether two Object instances are equal.
    /// </summary>
    /// <param name="obj">An <see cref="System.Object">Object</see> to compare with this instance.</param>
    /// <returns></returns>
    /// <seealso cref="System.Object">System.Object</seealso> 
    public override bool Equals(object obj)
    {
      if (object.ReferenceEquals(obj, null))
      {
        return false;
      }

      if (object.ReferenceEquals(this, obj))
      {
        return true;
      }

      FastBigNumber c = (FastBigNumber)obj;
      if (this.m_digits.DataUsed != c.m_digits.DataUsed)
      {
        return false;
      }

      for (int idx = 0; idx < this.m_digits.DataUsed; idx++)
      {
        if (this.m_digits[idx] != c.m_digits[idx])
        {
          return false;
        }
      }
      return true;
    }

    /// <summary>
    /// Returns the hash code for this instance.
    /// </summary>
    /// <returns>A 32-bit signed integer has code.</returns>
    /// <seealso cref="System.Object">System.Object</seealso> 
    public override int GetHashCode()
    {
      return this.m_digits.GetHashCode();
    }

    /// <summary>
    /// Converts the numeric value of this instance to its equivalent base 10 string representation.
    /// </summary>
    /// <returns>A <see cref="System.String">String</see> in base 10.</returns>
    /// <seealso cref="System.Object">System.Object</seealso> 
    public override string ToString()
    {
      return ToString(10);
    }
    #endregion

    #region Type Conversion Methods
    /// <summary>
    /// Converts the numeric value of this instance to its equivalent string representation in specified base.
    /// </summary>
    /// <param name="radix">Int radix between 2 and 36</param>
    /// <returns>A string.</returns>
    public string ToString(int radix)
    {
      if (radix < 2 || radix > 36)
      {
        throw new ArgumentOutOfRangeException("radix");
      }

      if (IsZero)
      {
        return "0";
      }

      FastBigNumber quotient;
      FastBigNumber remainder;
      FastBigNumber biRadix = new FastBigNumber(radix);
      DigitsArray tempDigitArray = new DigitsArray(m_digits);

      const string charSet = "0123456789abcdefghijklmnopqrstuvwxyz";
      System.Collections.ArrayList al = new System.Collections.ArrayList();
      quotient = this;
      while (!quotient.IsZero)
      {
        Divide(quotient, biRadix, out quotient, out remainder);
        al.Insert(0, charSet[(int)remainder.m_digits[0]]);
      }

      string result = new String((char[])al.ToArray(typeof(char)));
      if (radix == 10 && IsNegative)
      {
        return "-" + result;
      }

      return result;
    }

    /// <summary>
    /// Returns string in hexidecimal of the internal digit representation.
    /// </summary>
    /// <remarks>
    /// This is not the same as ToString(16). This method does not return the sign, but instead
    /// dumps the digits array into a string representation in base 16.
    /// </remarks>
    /// <returns>A string in base 16.</returns>
    public string ToHexString()
    {
      System.Text.StringBuilder sb = new System.Text.StringBuilder();
      sb.AppendFormat("{0:X}", m_digits[m_digits.DataUsed - 1]);

      string f = "{0:X" + (2 * DigitsArray.DataSizeOf) + "}";
      for (int i = m_digits.DataUsed - 2; i >= 0; i--)
      {
        sb.AppendFormat(f, m_digits[i]);
      }

      return sb.ToString();
    }

    /// <summary>
    /// Returns FastBigNumber as System.Int16 if possible.
    /// </summary>
    /// <param name="value"></param>
    /// <returns>Int value of FastBigNumber</returns>
    /// <exception cref="System.Exception">When FastBigNumber is too large to fit into System.Int16</exception>
    public static int ToInt16(FastBigNumber value)
    {
      if (object.ReferenceEquals(value, null))
      {
        throw new ArgumentNullException("value");
      }
      return System.Int16.Parse(value.ToString(), System.Globalization.NumberStyles.Integer, System.Globalization.CultureInfo.CurrentCulture);
    }

    /// <summary>
    /// Returns FastBigNumber as System.UInt16 if possible.
    /// </summary>
    /// <param name="value"></param>
    /// <returns></returns>
    /// <exception cref="System.Exception">When FastBigNumber is too large to fit into System.UInt16</exception>
    public static uint ToUInt16(FastBigNumber value)
    {
      if (object.ReferenceEquals(value, null))
      {
        throw new ArgumentNullException("value");
      }
      return System.UInt16.Parse(value.ToString(), System.Globalization.NumberStyles.Integer, System.Globalization.CultureInfo.CurrentCulture);
    }

    /// <summary>
    /// Returns FastBigNumber as System.Int32 if possible.
    /// </summary>
    /// <param name="value"></param>
    /// <returns></returns>
    /// <exception cref="System.Exception">When FastBigNumber is too large to fit into System.Int32</exception>
    public static int ToInt32(FastBigNumber value)
    {
      if (object.ReferenceEquals(value, null))
      {
        throw new ArgumentNullException("value");
      }
      return System.Int32.Parse(value.ToString(), System.Globalization.NumberStyles.Integer, System.Globalization.CultureInfo.CurrentCulture);
    }

    /// <summary>
    /// Returns FastBigNumber as System.UInt32 if possible.
    /// </summary>
    /// <param name="value"></param>
    /// <returns></returns>
    /// <exception cref="System.Exception">When FastBigNumber is too large to fit into System.UInt32</exception>
    public static uint ToUInt32(FastBigNumber value)
    {
      if (object.ReferenceEquals(value, null))
      {
        throw new ArgumentNullException("value");
      }
      return System.UInt32.Parse(value.ToString(), System.Globalization.NumberStyles.Integer, System.Globalization.CultureInfo.CurrentCulture);
    }

    /// <summary>
    /// Returns FastBigNumber as System.Int64 if possible.
    /// </summary>
    /// <param name="value"></param>
    /// <returns></returns>
    /// <exception cref="System.Exception">When FastBigNumber is too large to fit into System.Int64</exception>
    public static long ToInt64(FastBigNumber value)
    {
      if (object.ReferenceEquals(value, null))
      {
        throw new ArgumentNullException("value");
      }
      return System.Int64.Parse(value.ToString(), System.Globalization.NumberStyles.Integer, System.Globalization.CultureInfo.CurrentCulture);
    }

    /// <summary>
    /// Returns FastBigNumber as System.UInt64 if possible.
    /// </summary>
    /// <param name="value"></param>
    /// <returns></returns>
    /// <exception cref="System.Exception">When FastBigNumber is too large to fit into System.UInt64</exception>
    public static ulong ToUInt64(FastBigNumber value)
    {
      if (object.ReferenceEquals(value, null))
      {
        throw new ArgumentNullException("value");
      }
      return System.UInt64.Parse(value.ToString(), System.Globalization.NumberStyles.Integer, System.Globalization.CultureInfo.CurrentCulture);
    }
    #endregion

    #region IComparable<FastBigNumber> Members

    int IComparable<FastBigNumber>.CompareTo(FastBigNumber other)
    {
      return CompareTo(other);
    }

    #endregion

    #region Public Functions and Properties
    public bool IsEven
    {
      get
      {
        if ((m_digits[0] & 1) == 0)
          return true;
        return false;
      }
    }

    public bool IsOdd
    {
      get
      {
        return !IsEven;
      }
    }
    #endregion

    #region IBigNumber Members

    public IBigNumber IAdd(IBigNumber second)
    {
      FastBigNumber sSecond = second as FastBigNumber;
      return this + sSecond;
    }

    public IBigNumber ISub(IBigNumber second)
    {
      FastBigNumber sSecond = second as FastBigNumber;
      return this - sSecond;
    }

    public IBigNumber IMul(IBigNumber second)
    {
      FastBigNumber sSecond = second as FastBigNumber;
      return this * sSecond;
    }

    public IBigNumber IDiv(IBigNumber second)
    {
      FastBigNumber sSecond = second as FastBigNumber;
      return this / sSecond;
    }

    public IBigNumber IMod(IBigNumber second)
    {
      FastBigNumber sSecond = second as FastBigNumber;
      return this % sSecond;
    }

    public IBigNumber IClone()
    {
      return new FastBigNumber(this);
    }

    public IBigNumber IConstruct(string number)
    {
      return new FastBigNumber(number);
    }

    public void IAbs()
    {
      IsNegative = false;
    }

    public bool IEqual(IBigNumber second)
    {
      return this == (second as FastBigNumber);
    }

    public bool ISmaller(IBigNumber second)
    {
      return this < (second as FastBigNumber);
    }
    #endregion

    #region Serialization
    
    public static void Serialize(FastBigNumber number, BinaryWriter writer)
    {
      if (!writer.BaseStream.CanWrite) throw new ArgumentException("The writer you provided is not writable");
      
      int count = number.m_digits.Count;
      if (number.IsNegative) count = -count;
      writer.Write(count);
      number.m_digits.Serialize(writer);
      SHA1 sha = new SHA1CryptoServiceProvider(); 

      byte[] data = sha.ComputeHash(Encoding.Default.GetBytes(number.ToHexString()));
      writer.Write(data);
    }

    public static FastBigNumber Deserialize(BinaryReader reader)
    {
      if (!reader.BaseStream.CanRead) throw new ArgumentException("The reader you provided is not readable");
      try
      {
        FastBigNumber result = new FastBigNumber();
        int count = reader.ReadInt32();

        if (count < 0) result.m_Negative = true;
        count = Math.Abs(count);
        result.m_digits.Deserialize(reader, count);
        SHA1 sha = new SHA1CryptoServiceProvider();
        byte[] checkSum = sha.ComputeHash(Encoding.Default.GetBytes(result.ToHexString()));
        byte[] data = reader.ReadBytes(checkSum.Length);
        for (int i = 0; i < checkSum.Length; i++)
        {
          if (data[i] != checkSum[i]) throw new IOException("Error deserializing FastBigNumber " + result.ToString());
        }

        return result;
      }
      catch (EndOfStreamException e)
      {
        throw new IOException("Unable to deserialize a FastBigNumber from a file");
      }
    }

    #endregion
  }
}

